/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/next-permutation-ii
   @Language: C++
   @Datetime: 16-02-09 08:19
   */

class Solution {
public:
	/**
	 * @param nums: a vector of integers
	 * @return: do not return anything, modify nums in-place instead
	 */
	/** Tips : See problem 52 : Next Permutation
	 * */
	void nextPermutation(vector<int> &nums) {
		// Method 1 : STL Algorithm
		// next_permutation(nums.begin(),nums.end());
		// Method 2 : do it by yourself
		if (nums.size()<2) return;
		vector<int>::iterator i, j, k;
		for (i=nums.end()-1; i!=nums.begin();){
			j = i--;    // find last increasing pair (i,i+1)
			if (!(*i < *j)) continue;
			// find last k which not less than i,
			for (k=nums.end(); !(*i < *(--k)););
			iter_swap(i,k);
			// now the range [j,end) is in descending order
			reverse(j,nums.end());
			return;
		}
		// current nums is in desending order
		reverse(nums.begin(),nums.end());
		return;
	}
};
